8. 无限集

无限集的“大小”

我们此处需要重新引入先前介绍的通过构造集合之间的关系来比较有限集基数的方法，并将它们推广到任意集合。因此，对于任意集合 $A$ 与 $B$：

• 若存在一个从 $A$ 到 $B$ 的 双射，记作 $A\text{bij}B$，则 $|A|=|B|$。
• 若存在一个从 $A$ 到 $B$ 的 满射函数，记作 $A\text{surj}B$，则 $|A|\ge |B|$。
• 若存在一个从 $A$ 到 $B$ 的 单射、全映射 关系，记作 $A\text{inj}B$，则 $|A|\le |B|$。
• 如果 $A\text{surj}B$ 不成立，称 $A$ 严格小于 $B$，记作 $A\text{strict}B$，此时 $|A|<|B|$。

现在我们就可以推导一些基本的比较无限集基数的定理了，这是先前提到的一些对有限集和无限集都适用的定理：

• 若 $A\text{bij}B$ 且 $B\text{bij}C$，则 $A\text{bij}C$，即 $|A|=|C|$。
• 若 $A\text{surj}B$ 且 $B\text{surj}C$，则 $A\text{surj}C$，即 $|A|\ge |C|$。
• 若 $A\text{surj}B$ 且 $B\text{surj}A$，则 $A\text{bij}B$，即 $|A|=|B|$。

最后一条看似十分显然但并不是这样，无论是 $A$ 到 $B$ 的满射函数还是 $B$ 到 $A$ 的满射函数都无法直接得出一个双射。

现在我们需要抛弃一些对有限集适用的直觉，指出有限集与无限集之间最大的区别：在无限集中添加一定量元素不会让集合变大。即，设 $A$ 为一个集合且 $b\notin A$，则 $A$ 是无限集当且仅当 $|A|=|A+\{b\}|$。

例如，考虑非负整数集集合 $\mathbb{N}$ 与正整数集合 ${\mathbb{N}}_{\mathbb{+}}$，很容易构造一个双射 $R$，其中对任意 $m\in \mathbb{N}$ 有 $mR(m+1)$。

我们称一个集合是 可数的，当且仅当集合中的元素可以按某种顺序排列。如果集合 $C$ 满足 $\mathbb{N}\text{bij}C$，即 $|\mathbb{N}|=|C|$ 时，称 $C$ 是 可数无限集。当一个集合是有限集或可数无限集时，集合是可数的。

为了证明一个集合是可数的，我们有引理：集合 $C$ 是可数的当且仅当 $\mathbb{N}\text{surj}C$。

该引理的正确性根据基数的定义显然。根据该引理很容易得到一个推论：集合 $C$ 是可数的当且仅当 $S\text{surj}C$，其中 $S$ 为可数集。

最基本的可数无限集是 $\mathbb{N}$。与此同时，集合 $\mathbb{Z}$、$\mathbb{Q}$、$\mathbb{N}\times \mathbb{N}$ 都可以依据上面给出的方法证明是可数无限集。

由于向无限集中添加一个元素不会改变其基数，显然向其添加有限个元素也不会改变其基数，再进一步，我们有结论：

向无限集中添加可数无穷个元素不会改变其大小。

通过这条结论，似乎可以意识到可数无限集是“最小”的无限集，即：设 $A$ 为任意无限集，$B$ 为可数无限集，则 $|A|\ge |B|$。

康托通过 对角线证明 证明的 康托定理 指出并不是所有无限集的基数都是相同的。具体而言对任意集合 $A$，$|A|<|\mathrm{pow}(A)|$。也因此，不存在一个最大的集合。

这是康托对角线证明的简单说明：

我们设函数 $f$ 是从 $A$ 到 $\mathrm{pow}(A)$ 的任意函数，需要证明 $f$ 一定不是满射函数，即存在一个 $A$ 的子集不落在 $f$ 的值域中。考虑这样一个集合

显然 $D\subseteq A$，即 $D\in \mathrm{pow}(A)$。假设 $D$ 落在 $f$ 的值域中，则存在一些元素 $q\in A$ 满足 $D=f(q)$。但由于 $D$ 的定义，对于任意 $a\in A$，若 $a\in D$，则 $a\notin f(a)$。令 $a=q$，则得到结论：若 $q\in D$，则 $q\notin D=f(q)$，显然自相矛盾。故假设不成立，$D$ 一定不落在 $f$ 的值域中，因此对于任意的函数 $f$，都不是满射的。

将其表示成图表的形式如下：

因此我们知道，$\mathbb{N}\text{strict}\mathrm{pow}(\mathbb{N})$，因此 $\mathrm{pow}(\mathbb{N})$ 是 不可数 的。由于我们先前 证明过 $|\mathrm{pow}(\mathbb{N})|=\{0,1{\}}^{\omega }$，因此二进制数构成的无限集 $\{0,1{\}}^{\omega }$ 也是不可数的。

基于上面提到的比较集合基数的定理，我们很容易得出下面两条用于从已知是否可数的集合推断其他集合是否可数的推论：

• 若集合 $S$ 是可数的且 $S\text{surj}C$，则集合 $C$ 是可数的。
• 若集合 $S$ 是不可数的且 $C\text{surj}S$，则集合 $S$ 是不可数的。

基于这条推论，我们可以证明实数集 $\mathbb{R}$ 是 不可数的。

图灵停机问题

推荐观看：

• 停机悖论三句话就能证明不完备性定理？ —— 漫士
• 数学有一个致命的缺陷 —— 真理元素。

关于可数无穷与不可数无穷的分析对于计算理论至关重要。考虑这样一个事实。我们不妨称一个二进制串 $s$ 是 可计算的，当且仅当存在一个程序能够计算出其任意一位上的值。而在现在的视角来看，程序只是由 有限 个字符（可能是 ASCII 字符或 UTF-8 字符）组成的字符串，因此我们能够写出 可数个 用于计算二进制串的程序，也因此只有可数个二进制串是可计算的。由于 $\{0,1{\}}^{\omega }$ 是不可数无穷大的，因此有不可数无穷多个二进制串不是可计算的。这表明，我们很有可能无法完美解决一些在编程中看似简单的问题，例如执行完美的类型检查，进行某些运行时检查来判断程序会不会发生错误等。本节将以计算理论中一个十分经典的问题——图灵停机问题来说明这点。

给定一个程序与初始参数，判断该程序最终是否能够终止并给出结果，还是永远不会停止执行，这就是图灵停机问题。图灵在提出此问题时已经证明：图灵停机问题是 不可判定的，即不存在一个程序能够判定任意的程序最终能否终止。其证明过程大致如下：

为了方便表述，不妨认为所有程序都有一个由字符串表示的程序定义。我们称由字符串 $s$ 定义的程序 $P_s$ 接受一个有限长的字符串作为参数，返回一个结果并停机，或是永远运行下去。假设存在这样一个程序 $Q$，其接受一个字符串，并判断该字符串所定义的程序是否会停机。若会停机，输出 YES，并停机；若不会停机，输出 NO，同样停机。

此时考虑这样一个程序 $Q^{\prime }$，其同样接受一段程序代码，行为为：给定一个字符串 $s$，若 $Q(s)$ 输出 YES，则 $Q^{\prime }(s)$ 无限执行下去不会停机；若 $Q(s)$ 输出 NO，则 $Q^{\prime }(s)$ 输出 YES 并停机。将 $Q^{\prime }$ 的字符串表示 $t$ 输入给 $Q^{\prime }$，很容易发现矛盾：

• 若 $Q(t)$ 输出 YES 认为 $Q^{\prime }$ 会停机，则 $Q^{\prime }$ 无限执行下去不会停机；
• 若 $Q(t)$ 输出 NO 认为 $Q^{\prime }$ 不会停机，则 $Q^{\prime }$ 输出 YES 并停机。

无论何种情况都会产生矛盾，因此假设不成立，$Q$ 不存在。没有一个程序能够判断所有图灵机是否会停机，停机问题是不可判定的。应用该结论，可以证明不存在任何能够完美检查程序运行时的任何基于全局运行行为的性质的程序（基于部分运行行为的性质是可以被完美识别并因此制作对应的检查器的），因为任何这样的程序都可以用于构建一个判定停机的程序，而后者已被证明是不存在的。

罗素悖论与集合的 ZFC 公理系统

推荐观看：这位先生差点摧毁了数学 —— 真理元素。

自指 是一个十分常见但在数学中十分棘手的存在。例如，我们无法判定命题“这个命题是假命题”的真假性；再者，我们有大名鼎鼎的 罗素悖论：

设 $S$ 为任意集合，定义集合 $W$ 为所有 不包含自身 的集合：

那么，对于集合 $W$，很容易得出悖论 $W\in W\leftrightarrow W\notin W$。

解决罗素悖论的一个简单方法是规定 $W$ 不能是集合。但 $W$ 是经严谨的数学表述定义的，这就给应用中判断何者究竟为集合带来了问题。不过后来数学家建立了一套更简单并广泛使用的集合论公理化方法，并避免了罗素悖论，这套公理系统被称作 包含选择公理的策梅洛-弗兰克尔集合论公理系统，简称 ZFC 公理系统，其由如下公理组成：

• 外延公理
• 无序对公理
• 并集公理
• 无穷公理
• 子集公理
• 幂集公理
• 替换公理
• 基础公理
• 选择公理

ZFC 公理系统与公理的具体内容不在本课程要讨论、掌握的范围之内，不再列出。

ZFC 公理系统并非完美无缺，一些关于集合性质的基本问题仍然无法解决。例如，当前已经能够证明在这套公理体系下无法证明 康托连续统假设 的真伪。此外，基于这套公理体系也可以推出例如 巴拿赫-塔斯分球悖论 这样显然违反常识的结论。不过，古德尔第二不完备性定理指出，无法在一个拥有足够强算术公理的体系内部证明该公理的一致性。